package leetcode;

//给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//candidates 中的数字可以无限制重复被选取。
//说明：
//所有数字（包括 target）都是正整数。
//解集不能包含重复的组合。 

// 多元一次方程组

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class problems_039 {

    public static void main(String[] arge){
        new Solution().combinationSum(new int[]{2,1}, 2);
    }
    static class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            // 计算
            getNext(candidates, 0, target, new Integer[candidates.length]);
//            // 转换
//            for (int i = 0; i < listSolution.size(); i++) {
//                for (int j = 0; j < listSolution.get(i).size(); j++) {
//                    if(j != 0) System.out.print(",");
//                    System.out.print(listSolution.get(i).get(j));
//                }
//                System.out.println("");
//            }
            return listSolution;
        }

        /**
         * 回溯法解题
         */
        int number = 1;
        List<List<Integer>> listSolution = new ArrayList<List<Integer>>();
        public boolean getNext(int[] candidates, int index, int target, Integer[] solution){
            // 回溯到底，没算尽，则失败
            if(index >= candidates.length) return false;
            // 对象
            int num = candidates[index];
//            System.out.println("第" + (number++) + "次,index:" + index + ",target:" + target);
            // 遍历查找
            for (int i = 0; i <= target / num; i++) {
                int temp = target - (num * i);
                // 找到解决方案
                solution[index] = i;
                if(temp == 0) {
//                    System.out.print("--追加，:");
                    // 追加
                    List<Integer> list = new ArrayList();
                    for (int j = 0; j < solution.length; j++) {
                        if(null == solution[j] || 0 == solution[j]) continue;
//                        System.out.print("  " + candidates[j] + " X " + solution[j]);
                        for (int k = 0; k < solution[j]; k++) {
                            list.add(candidates[j]);
                        }
                    }
//                    System.out.println("");
                    listSolution.add(list);
                    solution[index] = null;
                }else {
                    if(!getNext(candidates, index + 1, temp, solution)){
                        solution[index] = null;
                    }
                }
            }
            return false;
        }
    }
}
